package me.mingshan.leetcode;


import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicLong;

/**
 * https://leetcode.cn/problems/maximum-product-of-splitted-binary-tree
 *
 * 给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。
 *
 * 由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。
 *
 * @author hanjuntao
 * @date 2025/10/12 0012
 */
public class L_1339_分裂二叉树的最大乘积 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        System.out.println(maxProduct(root));
    }

    /**
     * 问题：
     * 这道题的关键问题是如何知道从哪个地方分裂，使左右子树的和是最大的。
     *
     * 左右子树和的乘积=左子树和 * 右子树和
     * 如果知道总和totalSum，那么右子树和 = totalSum - 左子树和
     *
     * 所以：左右子树和的乘积=左子树和 * (totalSum - 左子树和)
     *
     *
     * 思路：
     *
     * 1. 获取当前树的节点和，存储在sumMap中，并且得到总和totalSum
     * 2. 获取当前节点的左子树和，右子树和，并计算当前节点的子树和，并更新结果
     * 3. 递归处理左子树和右子树，并更新结果
     *
     *
     * @param root
     * @return
     */
    public static int maxProduct(TreeNode root) {
        // 获取当前树的节点和
        Map<TreeNode, Long> sumMap = new HashMap<>();
        long totalSum = dfs(root, sumMap);

        // 遍历树，获取最大乘积
        AtomicLong result = new AtomicLong();
        dfs2(root.left, totalSum, sumMap, result);
        dfs2(root.right, totalSum, sumMap, result);

        return (int) (result.get() % (int) (1e9 + 7));
    }

    private static void dfs2(TreeNode root, long totalSum, Map<TreeNode, Long> sumMap, AtomicLong result) {
        if (root == null) {
            return;
        }

        long leftValue = sumMap.get(root);
        long rightValue = totalSum - leftValue;

        result.set(Math.max(result.get(), leftValue * rightValue));

        dfs2(root.right, totalSum, sumMap, result);
        dfs2(root.left, totalSum, sumMap, result);
    }

    /**
     * 获取当前树的节点和
     *
     * @param root 树
     * @return 节点和
     */
    private static long dfs(TreeNode root, Map<TreeNode, Long> sumMap) {
        if (root == null) {
            return 0;
        }

        long left = dfs(root.left, sumMap);
        long right = dfs(root.right, sumMap);
        long sum = left + right + root.val;

        if (sumMap != null) {
            sumMap.put(root, sum);
        }
        return sum;
    }
}
